//
//  234. 回文链表.swift
//  Top600
//
//  Created by rjb on 2021/7/28.
//

import Foundation
class Solution234 {
    // 判定是否是回文链表
    // 先找到中间节点
    // 后面的节点进行反转
    func isPalindrome(_ head: ListNode?) -> Bool {
        let mid = midNode(head)
        let reversed = reversList(mid)
        var first = head
        var second = reversed
        var flag = true
        while first != nil && second != nil {
            if first?.val != second?.val {
                flag = false
            }
            first = first?.next
            second = second?.next
        }
        
        if flag && first == nil && second == nil {
            flag = true
        }
        return flag
    }
    // 取中间节点
    func midNode(_ head: ListNode?) -> ListNode? {
        var slow: ListNode? = head
        var fast: ListNode? = head
        while fast != nil {
            slow = slow?.next
            fast = fast?.next?.next
        }
        return slow
    }
    
    // 反转一个链表
    func reversList(_ head: ListNode?) -> ListNode? {
        var prev: ListNode?
        var curr: ListNode? = head
        while curr != nil {
            let nextTemp = curr?.next
            curr?.next = prev
            prev = curr
            curr = nextTemp
        }
        return prev
    }
    
    static func test() {
        let solution = Solution234()
        
        let node1 = ListNode(1)
        let node2 = ListNode(2)
        
        node1.next = node2
        
        let result = solution.isPalindrome(node1)
        print(result)
    }
}
